/*
@author: ty
@file: 二叉树.go
@time: 2022/12/7 15:13
*/
package main

import "fmt"

type TreeNode struct {
	Data  int    // 节点用来存放数据
	left  *TreeNode // 左子树
	right *TreeNode // 右字树
}
//(完全)二叉树结构
type Tree struct {
	rootnode *TreeNode
}
func (self *Tree) Add(data int) {
	var queue []*TreeNode
	newNode := &TreeNode{Data:data}
	if self.rootnode == nil {
		self.rootnode = newNode
	}else {
		queue = append(queue, self.rootnode)
		for len(queue) != 0 {
			cur := queue[0]
			queue = append(queue[:0], queue[0+1:]...)
			// 往右树添加
			if data > cur.Data {
				if cur.right == nil {
					cur.right = newNode
				} else {
					queue = append(queue, cur.right)
				}
				// 往左数添加
			} else {
				if cur.left == nil {
					cur.left = newNode
				} else {
					queue = append(queue, cur.left)
				}
			}
		}
	}
}
func (self *Tree)fshowall(head *TreeNode) {//遍历二叉树，先序遍历二叉树，先将传进来的指针进行输出指针所指向的值，再将指针指向的的左子树和右子树进行递归
	if head != nil {
		//先打印根节点
		fmt.Println(head.Data)
		//再打印左子树
		self.fshowall(head.left)
		//再打印右子树
		self.fshowall(head.right)
	}
}
func (self *Tree)mshowall(head *TreeNode){//中序遍历二叉树，先将传进来的指针进行判断是否为空，如果不为空，则先将指针指向的左树进行递归
	if head !=nil{
		//先打印左子树
		self.mshowall(head.left)
		// 再打印根节点
		fmt.Println(head.Data)
		//再打印右子树
		self.mshowall(head.right)
	}
}
func(self *Tree)lshowall(head *TreeNode){//后序遍历二叉树，先将左子树的指针传入，再进行递归
	if head !=nil{

		//先打印左子树
		self.lshowall(head.left)
		//再打印右子树
		self.lshowall(head.right)
		// 再打印根节点
		fmt.Println(head.Data)
	}
}
func main()  {
	tree := &Tree{}
	tree.Add(50)
	tree.Add(45)
	tree.Add(40)
	tree.Add(48)
	tree.Add(51)
	tree.Add(61)
	tree.Add(71)

	fmt.Println("前序遍历")
	tree.fshowall(tree.rootnode)
	fmt.Println("")
	fmt.Println("中序遍历")
	tree.mshowall(tree.rootnode)
	fmt.Println("")
	fmt.Println("后续遍历")
	tree.lshowall(tree.rootnode)
}
